`
https://leetcode.cn/problems/avoid-flood-in-the-city/
`

// https://datastructures-js.info/docs/binary-search-tree
const { AvlTree } = require('datastructures-js');

/**
 * @param {number[]} rains
 * @return {number[]}
 */
var avoidFlood = function (rains) {
  const n = rains.length
  const fullDay = new Map() // 湖泊 -> 装满日
  const dryDay = new AvlTree((a, b) => a - b); // 未被使用的抽水日
  const res = new Array(n).fill(-1)
  for (let i = 0; i < n; i++) {
    const r = rains[i]
    if (r === 0) {
      // 没下雨，先随便找个池子抽
      res[i] = 1
      dryDay.insert(i)
      continue
    }
    const rainDay = fullDay.get(r)
    if (rainDay !== undefined) {
      // 在 rainDay 之前把湖泊抽干
      // 找一个最早的未被使用的抽水日
      const node = dryDay.ceil(rainDay)
      // 如果找不到，则无解
      if (node === null) return []
      res[node.getValue()] = r
      dryDay.removeNode(node) // 移除已经使用过的抽水日
    }
    fullDay.set(r, i) // 更新湖泊装满的日期
  }
  return res
};